home *** CD-ROM | disk | FTP | other *** search
/ Programmer Power Tools / Programmer Power Tools.iso / c / hsort.c < prev    next >
C/C++ Source or Header  |  1985-08-06  |  5KB  |  179 lines
  1. #define DEBUG
  2. /*    hsort - general purpose heapsort 
  3.  
  4.     Author...
  5.         Copyright (c) 1985  James R. Van Zandt
  6.  
  7.         All rights reserved.
  8.         This program may be copied for personal, non-profit use only.
  9.  
  10.         Based on algorithms by Jon Bentley [Communications of the ACM v
  11.         28 n 3 p 245 (Mar 85) and v 28 n 5 p 456 (May 85)], and the
  12.         sort interface routines by Allen I.  Holub [Dr.  Dobb's Journal
  13.         #102 (Apr 85)].
  14.  
  15.     Usage...
  16.  
  17.         Including a #define for DEBUG will make this file a stand-alone
  18.         program which sorts argv and prints the result, along with the
  19.         heap at the intermediate stages.  This is instructive if you
  20.         want to see how the heap sort works.  #defining DEBUG2 will
  21.         also print results of comparisons.
  22.  
  23.     Notes...
  24.         This routine sorts N objects in worst-case time proportional to
  25.         N*log(N).  The heapsort was discovered by J.  W.  J.  Williams
  26.         [Communications of the ACM v 7 p 347-348 (1964)] and is
  27.         discussed by D.  E.  Knuth [The Art of Computer Programming,
  28.         Volume 3: Sorting and Searching, Addison-Wesley, Reading,
  29.         Mass., 1973, section 5.2.3].
  30.  
  31.         This algorithm depends on a portion of an array having the
  32.         "heap" property.  The array X has the property heap[L,U] if:
  33.  
  34.             for all      L, i, and U
  35.             such that    2L <= i <= U
  36.             we have      X[i div 2] <= X[i]
  37.         
  38.         sift_down enlarges the heap: It accepts an array with heap[L+1,U]
  39.         and returns an array with heap[L,U].
  40. */
  41.  
  42. typedef int (*PFI)();        /* pointer to a function returning int    */
  43. static PFI Comp;            /* pointer to comparison routine        */
  44. static int Width;            /* width of an object in bytes            */
  45. static char *Base;            /* pointer to element [-1] of array        */
  46. static char *a, *b, tmp;    /* temporaries for exchanges            */
  47.  
  48. #ifdef DEBUG
  49. int Exchanges=0, Comparisons=0;
  50. #endif
  51.  
  52. /*--------------------------------------------------------------------------*/
  53. int argvcmp(s1p,s2p) char **s1p,**s2p;
  54. {
  55.     /*    Comparison routine for sorting an argv like list of pointers to
  56.         strings.  Just remove one level of indirection and call strcmp
  57.         to do the comparison                                                */
  58.  
  59. #ifdef DEBUG
  60.     Comparisons++;
  61. #endif
  62. #ifdef DEBUG2
  63.     register int rval;
  64.     rval=strcmp(*s1p,*s2p);
  65.     printf("   argvcmp(<%s><%s>) = %d\n",*s1p,*s2p,rval);
  66.     return (rval);
  67. #else
  68.     return (strcmp(*s1p,*s2p));
  69. #endif
  70. }
  71.  
  72. hsort(base,nel,width,compare)
  73. char *base;
  74. int    nel,width;
  75. int    (*compare)();
  76. {
  77. static int i,j,n,stop;
  78.     /*    Perform a heap sort on an array starting at base.  The array is
  79.         nel elements large and width is the size of a single element in
  80.         bytes.  Compare is a pointer to a comparison routine which will
  81.         be passed pointers to two elements of the array.  It should
  82.         return a negative number if the left-most argument is less than
  83.         the rightmost, 0 if the two arguments are equal, a positive
  84.         number if the left argument is greater than the right.  (That
  85.         is, it acts like a "subtract" operator.) If compare is 0 then
  86.         the default comparison routine, argvcmp (which sorts an
  87.         argv-like array of pointers to strings), is used.                    */
  88.  
  89. #ifdef DEBUG
  90.     static int ii;
  91.     printf("Sorting %d element array of %d byte elements at 0x%x\n",
  92.         nel,width,base);
  93.     printf("Comparison routine at 0x%x. Unsorted list:\n",compare);
  94.     ptext(1,nel,base);
  95.     for ( ii=1 ; ii<=nel ; ii++ ) printf("[%d]     ",ii);
  96.     printf("\n");
  97. #endif
  98.     Width=width;
  99.     Comp=(compare==(PFI)0) ? &argvcmp : compare ;
  100.     n=nel*Width;
  101.     Base=base-Width;
  102.     for (i=(n/Width/2)*Width; i>=Width; i-=Width) sift_down(i,n);
  103. #ifdef DEBUG
  104.     printf("Heap constructed\n");
  105.     for ( ii=1 ; ii<=nel ; ii++ ) printf("[%d]     ",ii);
  106.     printf("\n");
  107. #endif
  108.     stop=Width+Width;
  109.     for (i=n; i>=stop; )
  110.         {for (b=base, a=Base+i, j=Width ; j-- ; )
  111.             {tmp = *b; *b++ = *a; *a++ = tmp;
  112.             }
  113. #ifdef DEBUG
  114.         Exchanges++;
  115. #endif
  116.         sift_down(Width,i-=Width);
  117.         }
  118.  
  119. #ifdef DEBUG
  120.     printf("\nSort complete, list is:\n");
  121.     ptext(1,nel,base);
  122.     printf("%d comparisons and %d exchanges were performed \n",
  123.     Comparisons,Exchanges);
  124. #endif
  125. }
  126.  
  127. /*---------------------------------------------------------------------------*/
  128. static sift_down(L,U) int L,U;
  129. /*    pre: heap(L+1,U)        */
  130. {    int c,count;
  131.  
  132. #ifdef DEBUG
  133.     int i1;
  134.     i1=L;
  135. #endif
  136.     while(1)
  137.         {c=L+L;
  138.         if(c>U) break;
  139.         if( (c+Width <= U) && ((*Comp)(Base+c+Width,Base+c)>0) ) c+= Width;
  140.         if ((*Comp)(Base+L,Base+c)>=0) break;
  141.         for(b=Base+L,a=Base+c,count=Width; count-- ; )
  142.             {tmp=*b; *b++ = *a; *a++ = tmp;
  143.             }
  144. #ifdef DEBUG
  145.         Exchanges++;
  146. #endif
  147.         L=c;
  148.         }
  149. #ifdef DEBUG
  150.     ptext(i1/2,U/2,Base+Width);
  151. #endif
  152. /*    post: heap(L,U)            */
  153. }
  154.  
  155. /*--------------------------------------------------------------------------*/
  156. /*        Test routine for hsort, compiled if DEBUG is #defined                */
  157.  
  158. #ifdef DEBUG
  159. static ptext( start, end, argv)
  160. int start,end;
  161. char **argv;
  162. {
  163.     /*    Print out argv, one element per line    */
  164.  
  165.     register int i;
  166.     for (i=1; i<start; i++) {printf("        "); argv++;}
  167.     for ( i=start ; i<=end ; i++ ) printf("%-8s",*argv++);
  168.     printf("\n");
  169. }
  170.  
  171. main(argc,argv) int argc; char **argv;
  172. {    
  173.     /*    Test routine for hsort.  Sorts argv (less the first element).    */
  174.  
  175.     hsort(++argv,--argc,sizeof(PFI),0);
  176. }
  177.  
  178. #endif
  179.